

import java.util.*;
public class SmartStrategy implements Strategy {
private	ArrayDeque<Integer> queueX;
private	ArrayDeque<Integer> queueY;
private Stack<String> stack;
private	int numerator[][];
private int width;
private int height;
private Thing map[][];
private int xPacman;
private int yPacman;
private LinkedList<String> Directions;

	private boolean CurrentStep()
	{
		int xMonster = queueX.poll();
		int yMonster = queueY.poll();
		boolean isFound = (xMonster == xPacman && yMonster == yPacman);
		if(isFound) return isFound;
		
		if((yMonster<height) && (numerator[xMonster][yMonster+1] == -1) && (map[xMonster][yMonster+1]== null || (map[xMonster][yMonster+1].getClass() != Wall.class)))
		{
			queueX.add(xMonster); 
			queueY.add(yMonster+1);
			numerator[xMonster][yMonster+1] = numerator[xMonster][yMonster]+1;
			stack.push("Up");
			isFound = (xMonster == xPacman && yMonster+1 == yPacman);
			if(isFound) return isFound;
		}
		
		if((yMonster>0) && (numerator[xMonster][yMonster-1] == -1) && (map[xMonster][yMonster-1]== null || (map[xMonster][yMonster-1].getClass() != Wall.class)))
		{
			queueX.add(xMonster); 
			queueY.add(yMonster-1);
			numerator[xMonster][yMonster-1]=numerator[xMonster][yMonster]+1; 
			stack.push("Down");
			isFound = (xMonster == xPacman && yMonster-1 == yPacman);
			if(isFound) return isFound;
		}
		
		
		
		if((xMonster>0) && numerator[xMonster-1][yMonster] == -1 && (map[xMonster-1][yMonster] == null || map[xMonster-1][yMonster].getClass() != Wall.class && numerator[xMonster-1][yMonster] == -1))
		{
			queueX.add(xMonster-1);
			queueY.add(yMonster);
			numerator[xMonster-1][yMonster ] = numerator[xMonster][yMonster]+1;
			stack.push("Right");
			isFound = (xMonster-1 == xPacman && yMonster == yPacman);
			if(isFound) return isFound;
		}
		
		if((xMonster<width-1) && numerator[xMonster+1][yMonster] == -1 && (map[xMonster+1][yMonster] == null || map[xMonster+1][yMonster].getClass() != Wall.class && numerator[xMonster+1][yMonster] == -1))
		{
			queueX.add(xMonster+1);
			queueY.add(yMonster);
			numerator[xMonster+1][yMonster] = numerator[xMonster][yMonster]+1;
			stack.push("Left");
			isFound = (xMonster+1 == xPacman && yMonster == yPacman);
			if(isFound) return isFound;
		}
		
		return false;
	}

	public String SelectDirection(Thing map[][], int xPacman, int yPacman, int xMonster, int yMonster)
	{
		Init(map,xPacman,yPacman,xMonster,yMonster);
		boolean isFound=false;
		numerator[xMonster][yMonster]=0; 
		while(!queueX.isEmpty()) 
			{
			isFound = CurrentStep();
			if(isFound) break;
			}
		if(!isFound) System.err.println("Monster is Blocked");
		if(!stack.isEmpty()) return stack.pop(); 
		else return "NotFound";
	}
	
	private void Init(Thing map[][], int xPacman, int yPacman, int xMonster, int yMonster) {
		//Coordinates of Pacman and Monster swaped consciously
		width = map.length;
		height = map[1].length; 
		this.map = map;
		this.xPacman = xPacman;
		this.yPacman = yPacman;
		if(queueX == null) queueX = new ArrayDeque<Integer>(width*height); else queueX.clear();
		if(queueY == null) queueY = new ArrayDeque<Integer>(width*height); else queueY.clear();
		if(stack == null) stack = new Stack<String>(); else stack.clear();
		if(Directions == null) Directions = new LinkedList<String>();
		if(!Directions.contains("Up")) Directions.add("Up");
		if(!Directions.contains("Right")) Directions.add("Right");
		if(!Directions.contains("Down")) Directions.add("Down");
		if(!Directions.contains("Left")) Directions.add("Left");
		queueX.add(xMonster);
		queueY.add(yMonster); 
		numerator = new int[width][height];
		for(int i=0;i<height;i++)
        	for(int j=0;j<map[0].length;j++)
        		numerator[i][j] = -1;
	}
	
	
}

